import com.sun.source.tree.Tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-09-22
 * Time: 20:08
 */
public class BinaryTree {
    class TreeNode {
        public Character val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(Character val) {
            this.val = val;
        }
    }
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        //E.right = H;
        return A;
    }
    public int i = 0;
    public TreeNode createTree(String str) {
        TreeNode root = null;
        if(str.charAt(i) != '#') {
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }
    // 前序遍历
    public void preOrder(TreeNode root)
    {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    //二叉树前序非递归遍历实现--遍历思路
    List<Character> list = new ArrayList<>();
    public void preorderTraversal0(TreeNode root) {
        if(root == null) {
            return;
        }
        list.add(root.val);
        preorderTraversal0(root.left);
        preorderTraversal0(root.right);
    }
    //二叉树前序非递归遍历实现--子问题思路
    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root == null) {
            return list;
        }
        list.add(root.val);
        List<Character> leftList = preorderTraversal(root.left);
        list.addAll(leftList);
        List<Character> rightList = preorderTraversal(root.right);
        list.addAll(rightList);
        return list;
    }
    //二叉树前序非递归遍历实现
    public List<Character> preorderTraversal2(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while( cur != null || !stack.isEmpty()) {
            while( cur != null) {
                res.add(cur.val);
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return res;
    }

    // 中序遍历
    public void inOrder(TreeNode root)
    {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    //二叉树中序非递归遍历实现
    public List<Character> inorderTraversal(TreeNode root) {
        List<Character> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while( cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            res.add(top.val);
            cur = top.right;
        }
        return res;
    }
    // 后序遍历
    public void postOrder(TreeNode root)
    {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    //二叉树中序非递归遍历实现

    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root == null) return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right == null || top.right == prev) {
                list.add(top.val);
                prev = top;
                stack.pop();
            }else {
                cur = top.right;
            }
        }
        return list;
    }

    // 获取树中节点的个数
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return size(root.left)
                + size(root.right) + 1;
    }
    // 获取叶子节点的个数--遍历思路
    public static int leafNodeCount = 0;
    public void getLeafNodeCount0(TreeNode root) {
        if(root == null) {
            return;
        }
        if(root.left == null && root.right == null) {
            leafNodeCount++;
        }
        getLeafNodeCount0(root.left);
        getLeafNodeCount0(root.right);
    }
    // 获取叶子节点的个数--子问题思路
    public int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.left == null) {
            return 1;
        }
        return getLeafNodeCount(root.left)
                + getLeafNodeCount(root.right);
    }

    // 获取第K层节点的个数
    int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)
                +getKLevelNodeCount(root.right,k-1);
    }

    /**
     * 获取二叉树的高度
     * 时间复杂度O(N)
     * @param root
     * @return
     */
    int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.max(leftHeight,rightHeight) + 1;
    }

    /**
     * 检测值为value的元素是否存在
     * 时间复杂度O(N)
     * 空间复杂度O(logN)
     * @param root
     * @param val
     * @return
     */
    TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
        TreeNode leftVal = find(root.left,val);
        if(leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = find(root.right,val);
        if(rightVal != null) {
            return rightVal;
        }
        return null;
    }

    /**
     * 检查两颗树是否相同
     * 假设p的节点数为n,q的节点数为m
     * 时间复杂度O(min.(n,m))
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //先判断结构是否一致
        if(p == null && q != null || p != null && q == null) {
            return false;
        }
        //此时要么都为空，要么都不为空
        if(p == null && q == null) {
            return true;
        }
        //此时都不为空 判断值是否相同
        if(p.val != q.val) {
            return false;
        }
        //都不为空，且值相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

    /**
     * 另一颗树的子树
     * 假设root的节点数为r，subRoot的节点数为s
     * 时间复杂度O(r*s)
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null) {
            return false;
        }
        //判断当前子树和根节点是否相同
        if(isSameTree(root,subRoot)) return true;
        //判断子树和当前root的左子树是否一样
        if(isSubtree(root.left,subRoot)) return true;
        //判断子树和当前root的右子树是否一样
        if(isSubtree(root.right,subRoot)) return true;
        return false;
    }

    /**
     * 翻转二叉树
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        //当节点的左右子树都为null，则没有必要交换，直接返回该节点即可
        if(root.left == null && root.right == null) {
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    //对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        if(leftTree == null && rightTree != null
                ||leftTree != null && rightTree == null) {
            return false;
        }
        if(leftTree == null && rightTree == null) {
            return true;
        }
        if(leftTree.val != rightTree.val) {
            return false;
        }
        return isSymmetricChild(leftTree.left,rightTree.right)
                && isSymmetricChild(leftTree.right,rightTree.left);
    }

    //

    /**
     * 判断是否为平衡树：左树和右树之差的绝对值<2
     * 时间复杂度O(N*N)
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(Math.abs(leftHeight - rightHeight) >= 2) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);
    }

    /**
     * 判断是否为平衡树：左树和右树之差的绝对值<2
     * 时间复杂度O(N)
     * @param root
     * @return
     */
    public boolean isBalanced2(TreeNode root) {
        if(root == null) {
            return false;
        }
        return getHeight2(root) >= 0;
    }
    public int getHeight2(TreeNode root) {
        if(root == null) return 0;
        int leftHeight = getHeight2(root.left);
        if(leftHeight <0) {
            return -1;
        }
        int rightHeight = getHeight2(root.right);
        if(rightHeight != -1 && Math.abs(leftHeight - rightHeight) <2) {
            return Math.abs(leftHeight - rightHeight) + 1;
        }else {
            return -1;
        }
    }

    //二叉搜索树与双向链表
    TreeNode prev = null;
    public TreeNode Convert(TreeNode root) {
        if(root == null) {
            return null;
        }
        ConvertChild(root);
        TreeNode head = root;
        while(head.left != null) {
            head = head.left;
        }
        return head;
    }
    public void ConvertChild(TreeNode root) {
        if(root == null) return;
        ConvertChild(root.left);
        root.left = prev;
        if(prev != null) {
            prev.right = root;
        }
        prev = root;
        ConvertChild(root.right);
    }

    //层序遍历
    public void levelOrder0(TreeNode root) {
        if (root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
        System.out.println();
    }

    //层序遍历--从上往下，从左向右
    public List<List<Character>> levelOrder(TreeNode root) {
        List<List<Character>> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Character> list0 = new ArrayList<>();
            while (size != 0) {
                TreeNode cur = queue.poll();
                list0.add(cur.val);
                size--;
                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(list0);
        }
        return list;
    }

    //层序遍历--从下往上，从左向右
    public List<List<Character>> levelOrderBottom(TreeNode root) {
        List<List<Character>> list = new LinkedList<>();
        if(root == null) {
            return list;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Character> list0 = new LinkedList<>();
            int size = queue.size();
            for(int i = 0; i < size;i++) {
                TreeNode top = queue.poll();
                list0.add(top.val);
                if(top.left != null) {
                    queue.offer(top.left);
                }
                if(top.right != null) {
                    queue.offer(top.right);
                }
            }
            list.add(0,list0);
        }
        return list;
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return true;
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while(!queue.isEmpty()){
            if(queue.peek() != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }
    //两个节点的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
        if(root == null) return null;
        if(root == p || root == q) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode rightTree = lowestCommonAncestor(root.right,p,q);

        if(leftTree != null && rightTree != null) {
            //此时p,q分别在根的左右两边
            return root;
        }else if(leftTree != null) {
            //此时p,q都在左边
            return leftTree;
        }else {
            //此时p,q都在右边
            return rightTree;
        }
    }
    public TreeNode lowestCommonAncestor2(TreeNode root,TreeNode p,TreeNode q) {
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);
        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if(sizeP > sizeQ) {
            int size = sizeP - sizeQ;
            while (size != 0) {
                stackP.pop();
                size--;
            }
        }else {
            int size = sizeQ - sizeP;
            while (size != 0) {
                stackQ.pop();
                size--;
            }
        }
        while(!stackP.isEmpty() && !stackQ.isEmpty()) {
            if(stackP.peek() == stackQ.peek()) {
            //注意如果栈存放类型是Integer，要用equals,因为==判断Integer类型时是有一定范围的，如果超出了范围就会范围false
                return stackP.peek();
            }else {
                stackP.pop();
                stackQ.pop();
            }
        }
        return null;
    }
    private boolean getPath(TreeNode root,TreeNode node,Stack<TreeNode> stack) {
        if(root == null) {
            return false;
        }
        stack.push(root);
        if (root == node) {
            return true;
        }
        boolean ret = getPath(root.left,node,stack);
        if(ret == true) {
            return true;
        }
        ret = getPath(root.right,node,stack);
        if(ret == true) {
            return true;
        }
        stack.pop();
        return false;
    }

    //根据一棵树的前序遍历与中序遍历构造二叉树。
    public int preIndex;
    public TreeNode buildTree1(char[] preorder,char[] inorder) {
        return buildTreeChild1(preorder,inorder,0,preorder.length-1);
    }
    public TreeNode buildTreeChild1(char[] preorder,char[] inorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findVal1(inorder,inBegin,inEnd,preorder[preIndex]);
        preIndex++;
        root.left = buildTreeChild1(preorder,inorder,inBegin,rootIndex-1);
        root.right = buildTreeChild1(preorder,inorder,rootIndex+1,inEnd);
        return root;
    }
    public int findVal1(char[] inorder,int inBegin,int inEnd,int val) {
        for (int i = inBegin;i <= inEnd;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    //根据一棵树的中序遍历与后序遍历构造二叉树
    public int postIndex;
    public TreeNode buildTree2(char[] inorder, char[] postorder) {
        postIndex = postorder.length-1;
        return buildTreeChild2(inorder,postorder,0,postIndex);
    }
    public TreeNode buildTreeChild2(char[] inorder,char[] postorder,int inBegin,int inEnd) {
        if(inBegin > inEnd) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findVal2(inorder,inBegin,inEnd,postorder[postIndex]);
        postIndex--;
        root.right = buildTreeChild2(inorder,postorder,rootIndex+1,inEnd);
        root.left = buildTreeChild2(inorder,postorder,inBegin,rootIndex-1);
        return root;
    }
    private int findVal2(char[] inorder,int inBegin,int inEnd,int val) {
        for(int i = inBegin; i <= inEnd;i++) {
            if(inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

    //二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuilder sbd = new StringBuilder();
        tree2strChild(root,sbd);
        return sbd.toString();
    }
    public void tree2strChild(TreeNode root,StringBuilder sbd) {
        if(root == null) return;
        sbd.append(root.val);
        if(root.left != null) {
            sbd.append("(");
            tree2strChild(root.left,sbd);
            sbd.append(")");
        }else {
            if(root.right == null) {
                return;
            }else {
                sbd.append("()");
            }
        }
        if(root.right != null) {
            sbd.append("(");
            tree2strChild(root.right,sbd);
            sbd.append(")");
        }else {
            return;
        }
    }


}
